package chapter01_stackandqueue;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 描述：
 *      生成窗口内最大值
 * @author hl
 * @date 2021/1/15 9:40
 */
public class MaxInWindow {
    public static int[] getMaxWindow(int[] arr, int w){
        int len = arr.length;
        int[] res = new int[len - w + 1];
        LinkedList<Integer> qmax = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < len; i++) {
            //链表中从头到尾是递减的，忽略较小的值
            while(!qmax.isEmpty() && arr[qmax.peek()] <= arr[i]){
                qmax.pollLast();
            }
            //存放的是下标
            qmax.addLast(i);
            //判断队列头的下标是否过期
            if (i - w == qmax.peekFirst()) {
                qmax.pollFirst();
            }
            if (i >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4,3,5,4,3,3,6,7};
        System.out.println(Arrays.toString(getMaxWindow(arr, 3)));
    }
}
